#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define Status int
//栈，队列：操作受限制的线性表 
//串：内容受限制的线性表
//数组，广义表：非线性表(线性表结构的推广) 

//串(String)-----零个或者多个任意字符组成的有限序列 
//S = "a1a2a3...an" (n>=0)
//串名:S, 串值："a1a2a3...an"，串长：n   
//子串：一个串中任意个连续字符组成的子序列(含空串)称为该串的子串 
//真子串 是不包含自身的所有子串 
//主串：包含子串的串相应地称为主串
//字符位置：字符在序列中的序号为该字符在串中的位置 
//子串位置：子串第一个字符在主串中的位置
//空格串：由一个或多个空格组成的串，与空串不同 
//串相等：两个串长度相等，各个位置对应的字符也相等 

//串的基本操作  
//1. StrAssign(&T, chars) 串赋值
//2. StrCompare(S, T) 	 串比较
//3. StrLength(S)		 求串长
//4. Concat(&T, S1, S2)  串连结
//5. SubString(&Sub, S, pos, len) 求子串
//6. StrCopy(&T, S)     串拷贝
//7. StrEmpty(S)		串判空 
//8. ClearString(&S)    清空串
//9. Index(S, T, pos)   子串的位置 ***
//10. Replace(&S, T, V) 串替换
//11. StrInsert(&S, pos, T) 子串插入
//12. StrDelete(&S, pos, len) 子串删除 
//13. DestoryString(&S)  串销毁 


//串的顺序存储结构 (常用)
#define MAXLEN 255
typedef struct{
	char ch[MAXLEN + 1]; //存储串的一维数组
	int length; //串的当前长度 
}SString; 
//串的第一位通常存串的长度，不存字符。如下：  
Status StrAssign(SString &S, char str[]){
	int i = 0;
	while(str[i] != '\0'){
		S.ch[i+1] = str[i];
		i++;
	}
	S.ch[i+1] = '\0';
	S.ch[0] = i;
	S.length = i;
}

int StrLength(SString S){
	return S.ch[0];
	//return S.length;
}


void StrCopy(SString &S, SString T){
	strcpy(S.ch, T.ch);
	S.length = S.ch[0];
}

void PrintStr(SString S){
	for(int i = 1;i <= S.ch[0]; i++){
		//printf("%c",S.ch[i]);
		cout<<S.ch[i];
	}
	cout<<"\n";
}



//串的链式存储结构(不常用) 优点：操作方便   缺点：存储密度较低 (可以将多个字符存放在一个结点中，以克服其缺点)
//串的链式存储结构----块链结构 
#define CHUNKSIZE 80 //块的大小可以由用户定义
typedef struct Chunk{
	char ch[CHUNKSIZE];
	struct Chunk *next;
}Chunk;

typedef struct{
	//指针可以自己根据情况选择 
	Chunk *head;  //串的头指针 
	Chunk *tail;  //串的尾指针
	int curlen;   //串的当前长度 
}LString;  //字符串的块链结构 


//4.3.3串的模式匹配算法
//算法目的：确定主串所含子串(模式串)第一次出现的位置(定位) 
//算法应用：搜索引擎、拼写检查、语言翻译、数据压缩
//算法种类：
//	BF算法(Brute-Force，又称古典的、经典的、朴素的、穷举的)，暴力破解法,简单匹配算法。采用穷举法的思路 
//  KMP算法(特点：速度快) 


//BF算法设计思想  Index(S, T, pos)
//将主串的第pos个字符和模式串的第一个字符比较
//	若相等，继续逐个比较后续字符 
//  若不等，从主串的下一个字符起，重新与模式串的第一个字符比较 
//		直到主串的一个连续子串字符序列与模式串相等。返回值为S中与T匹配的子序列的第一个字符的序号，即匹配成功。
//		否则，则匹配失败，返回值0


//或者从pos位置开始 匹配的算法 
//int Index_BF(SString S, SString T, int pos){
//	int i = pos, j = 1;//下同 
//} 
int Index_BF(SString S, SString T){
	int i = 1, j = 1;
	//S.length等于S.ch[0],  T.length等于T.ch[0] 
	while(i <= S.length && j <= T.length){
		if(S.ch[i] == T.ch[j]){
			//主串和子串依次匹配下一个字符 
			i++;
			j++;
		}else{
			//匹配不成功 ，i,j回溯*****开始下一次匹配 
			i = i - j + 2; // i和j此时都移动了 i - 1 = j -1 位，要重新进入下一位字符开始的子串匹配 
			j = 1;
		}
	}
	if(j > T.length) return i - T.length; //返回匹配的第一个字符的下标 
	else return 0; //模式匹配失败，返回0 
}//时间复杂度O(n*m) 


//*********KMP(Knuth Morris Pratt)算法**********
//KMP算法设计思想：利用已经部分匹配的结果而加快模式串的滑动速度，且主串S的指针 i 不必回溯， 可提速到O(n+m)  
int Index_KMP(SString S, SString T, int pos){
	int i = pos, j = 1;
	while(i < S.length && j < T.length){
		if(j == 0 || S.ch[i] == T.ch[j]){
			i++;
			j++;
		}else{
			//j = next[j];   /*i不变，j后退*/
		}
	}
	if(j > T.length) return i - T.length; /*匹配成功*/
	else return 0;     /*返回不匹配的标志*/ 
}

void get_next(SString T, int &next[]){
	int i = 1, j = 0;
	next[1] = 0;
	while(i < T.length){
		if(j == 0 || T.ch[i] == T.ch[j]){
			++i;
			++j;
			next[i] = j;
		}else {
			j = next[j];
		}
	}
}

void get_nextval(SString T, int &nextval[]){
	iint i =1, j = 0;
	while(i < T.length){
		if(j == 0 || T.ch[i] == T.ch[j]){
			++i;
			++j;
			if(T.ch[i] != T.ch[j]) nextval[i] = j;
			else nextval[i] = nextval[j];
		}
		else j = nextval[j];
	}
}



int main(void)
{
	SString S, T;
	
	printf("请输入S字符串：");
	char s[MAXLEN],t[MAXLEN];
	cin>>s;
	StrAssign(*&S, s);
	printf("请输入T字符串：");
	cin>>t;
	StrAssign(*&T, t);
	puts("输入完成");
	cout<<"S = ";
	PrintStr(S);
	cout<<"T = ";
	PrintStr(T);
	puts("BF匹配T在S中的位置");
	int index = Index_BF(S, T);
	if(index) printf("匹配成功，index = %d",index);
	else puts("匹配失败咯"); 
	return 0;
}